package kyssion.leetcode.num51_100;

import java.util.ArrayList;
import java.util.List;

public class Code78_子集 {
    public static void main(String[] args) {
        List<List<Integer>> arrayList = new Code78_子集().subsets(new int[]{1, 2, 3});
        for (List<Integer> list : arrayList) {
            for (Integer i : list) {
                System.out.print(i + " ");
            }
            System.out.println();
        }
    }

    /**
     * 最快解法, 优化点就是让每一次向下递归都获得一个可以插入的值,不是产生无效步骤
     * @param nums
     * @return
     */
    public List<List<Integer>> subsets(int[] nums) {
        List<List<Integer>> result = new ArrayList<>();
        List<Integer> list = new ArrayList<>();
        result.add(list);
        int index = 0;
        subsets(index, nums, list, result);
        return result;
    }

    private void subsets(int index, int[] nums, List<Integer> list, List<List<Integer>> result) {
        if (index >= nums.length) {
            return;
        }
        while (index < nums.length) {
            list.add(nums[index]);
            result.add(new ArrayList<>(list));
            subsets(index + 1, nums, list, result);
            list.remove(list.size()-1);
            index++;
        }
    }

}
